package sorts;
/**
 * 取最后一个元素作为参考值
 * 最开始已处理区间为i=0，从头遍历 如果比参考值小 就放入已处理区间的最后i，然后i++
 * 一轮下来已处理区间的i位置需要更换成参考值，因为参考值已经是已处理里的最大值了
 * 已i为界限 继续分治处理两侧的数组
 * 参考值的选择很重要 决定了快排的时间复杂度，优化方式：三分取中，随机等方式
 * 三分取中：从区间的首、中、尾分别取一个数，比较大小，取中间值作为参考点。
 */
public class ZhangQuick {

  // 快速排序，a是数组，n表示数组的大小
  public static void quickSort(int[] a, int n) {
    quickSortInternally(a, 0, n-1);
  }

  // 快速排序递归函数，p,r为下标
  private static void quickSortInternally(int[] a, int p, int r) {
    if (p >= r) return;

    int q = partition(a, p, r); // 获取分区点
    quickSortInternally(a, p, q-1);
    quickSortInternally(a, q+1, r);
  }

  /**
   * 们通过游标i把A[p…r-1]分成两部分。
   * A[p…i-1]的元素都是小于pivot的，我们暂且叫它“已处理区间”，A[i…r-1]是“未处理区 间”。
   * 每次都从未处理的区间A[i…r-1]中取一个元素A[j]，与pivot对比，
   * 如果小于pivot，则将其加入到已处理区间的尾部，也就是A[i]的位置。
   * @param a
   * @param p
   * @param r
   * @return
   */
  private static int partition(int[] a, int p, int r) {
    int pivot = a[r];
    int i = p;
    for(int j = p; j < r; ++j) {
      if (a[j] < pivot) {
        if (i == j) {
          ++i;
        } else {
          int tmp = a[i];
          a[i++] = a[j];
          a[j] = tmp;
        }
      }
    }

    int tmp = a[i];
    a[i] = a[r];
    a[r] = tmp;

    System.out.println("i=" + i);
    return i;
  }

  public static void main(String[] args) {
    int[] a = {4,3,6,1,0,8,2};
    ZhangQuick.quickSort(a, 7);
  }
}
